[νλ‘κ·Έλλ° λνμμ λ°°μ°λ μκ³ λ¦¬μ¦ λ¬Έμ ν΄κ²° μ λ΅ - κ΅¬μ’ λ§]μ μ½κ³ μ 리ν POSTμ λλ€.
π‘ κ°κ΄
μ΄λ€ μμ μ΄ μ£Όμ΄μ‘μ λ μ»΄ν¨ν°κ° μ΄ μμ μ ν΄κ²°νλ λ°©λ²μ μκ³ λ¦¬μ¦μ΄λΌκ³ νλ€. λ λ€λ₯΄κ²λ, κ°μ μΌμ νλ μ¬λ¬ κ°μ§μ λ°©λ²μ΄ μ‘΄μ¬νλ€. μ΄λ μ£Όμ΄μ§ λ¬Έμ λ₯Ό ν΄κ²°νλ ν κ°μ§ λ°©λ²μ λͺ λ£νκ² μ¨λμ κ²μ μκ³ λ¦¬μ¦μ΄λΌκ³ νλ€.
μ΄λ¬ν μΈ‘λ©΄μμ, μ£Όκ΄μ μ΄κ±°λ λͺ¨νΈν κ²μ μκ³ λ¦¬μ¦μ΄λΌκ³ ν μ μλ€. "μμΈ μ μ΄μμμ μΆμ²μ κ°λ€." λΌλ μμλ₯Ό λ€μμ λ, λ€μμ μ λΉν μκ³ λ¦¬μ¦μ΄λΌκ³ ν μ μλ€.
- μ§νμ² 2νΈμ μ νκ³ μμ²μμΌλ‘ κ°λ€.
- μ§νμ² 1νΈμ μΌλ‘ κ°μνκ³ μ²λ리μμΌλ‘ κ°λ€.
- κ²½μΆμ μ νκ³ , μΆμ²μμμ λ΄λ¦°λ€.
νμ§λ§ λ€μμ κ²½μ°λ λ§€μ° μ£Όκ΄μ μ΄λ©°, λ°λΌμ λ³Έμ§μ μΌλ‘ λͺ¨νΈνκΈ°μ μκ³ λ¦¬μ¦μ΄λΌκ³ ν μ μλ€.
- κ°λꡬ μͺ½μΌλ‘ κ°λ λ²μ€λ₯Ό νλ€.
- λμμΈ λ²μ€ ν°λ―Έλ κ·Όμ²μ μ¨ κ² κ°μΌλ©΄ λ΄λ¦°λ€.
- μΆμ² μͺ½μΌλ‘ κ°λ λ²μ€λ₯Ό νκ³ , νμ°Έ κ°λ€ λ΄λ¦°λ€.
ν λ¬Έμ λ₯Ό ν΄κ²°νλ λ° μ¬λ¬ κ°μ μκ³ λ¦¬μ¦μ΄ μμ μ μλ€. κ·Έλ λ€λ©΄ μ΄λ ν μκ³ λ¦¬μ¦μ λ§λ€μ΄μΌ ν κΉ? μκ³ λ¦¬μ¦μ λν νκ° κΈ°μ€μ "μκ°"κ³Ό "곡κ°"μ΄ μλ€.
-
μκ°
- μκ³ λ¦¬μ¦μ΄ μ μ μκ°μ μ¬μ©νλ€ = λ λΉ λ₯΄κ² λμνλ€
- μκ³ λ¦¬μ¦μ μν μλμ νΉμ±μ λΆμνλ λ₯λ ₯μ λ°°μν νμκ° μλ€.
-
곡κ°
- μκ³ λ¦¬μ¦μ΄ μ μ 곡κ°μ μ¬μ©νλ€ = λ μ μ μ©λμ λ©λͺ¨λ¦¬λ₯Ό μ¬μ©νλ€
- μ΄λ‘ μ μΌλ‘ μ무리 λΉ λ₯΄λλΌλ λ무 λ§μ λ©λͺ¨λ¦¬ 곡κ°μ μꡬνλ€λ©΄ μνν μ μμ κ²μ΄λ€.
λ νκ° κΈ°μ€μ μλ‘ μμΆ©λμ΄ tradeoffλ₯Ό λ°μμν€λ κ²½μ°κ° λ§λ€. μ΄νμ λμ¬ μκ³ λ¦¬μ¦λ€μμ λ€λ£¨λλ‘ νλ€.
π‘ μκ³ λ¦¬μ¦μ μκ° λ³΅μ‘λ λΆμ
π λμ
μ’ λ λΉ λ₯Έ μκ³ λ¦¬μ¦μ λ§λ€κΈ° μν΄μλ μκ³ λ¦¬μ¦μ μλλ₯Ό μ΄λ»κ² μΈ‘μ ν μ§μ λν κΈ°μ€μ μ ν΄μΌ νλ€. κ°μ₯ μ§κ΄μ μΈ λ°©λ²μ "κ°κ°μ νλ‘κ·Έλ¨μΌλ‘ ꡬνν λ€ κ°μ μ λ ₯μ λν΄ λ νλ‘κ·Έλ¨μ μν μκ°μ μΈ‘μ νλ κ²"μ΄λ€. μ€κ΅¬ν μ μ¬μ©μκ° λλΌκΈ°μ λ무 λ리λ€λ©΄ μμ©μ΄ μκΈ° λλ¬Έμ νμ€μ μΌλ‘λ μ μ©ν λ°©λ² μ€ νλμ΄λ€.
νμ§λ§ "νλ‘κ·Έλ¨μ μ€ν μκ°μ μκ³ λ¦¬μ¦μ μλλ₯Ό μΌλ°μ μΌλ‘ μ΄μΌκΈ°νλ κΈ°μ€μ΄ λκΈ°μλ λΆμ ν©"νλ€.
- νλ‘κ·Έλ¨μ μν μκ°μ μ¬μ©ν νλ‘κ·Έλλ° μΈμ΄, νλμ¨μ΄λ λ¬Όλ‘ μ΄κ³ μ΄μ체μ , μ»΄νμΌλ¬κΉμ§ μλ§μ μμμ μν΄ λ°λ μ μκΈ° λλ¬Έμ΄λ€.
-
νλ‘κ·Έλ¨μ μ€μ μν μκ°μ΄ λ€μν μ λ ₯μ λν μ€ν μκ°μ λ°μνμ§ λͺ»νλ λ¬Έμ λ μλ€.
- μκ³ λ¦¬μ¦μ μΈμ λ κ°μ μλλ‘ λμνλ κ²μ΄ μλλ©°, μ λ ₯μ ν¬κΈ°λ νΉμ±μ λ°λΌ μν μκ°μ΄ λ¬λΌμ§ μ μλ€.
λ°λ³΅λ¬Έμ΄ μ§λ°°νλ€
μλμ°¨ 2λκ° μκ³ , μμΈμμ λΆμ°κΉμ§ κ°λ €κ³ ν λ μ΄λ μλμ°¨λ₯Ό νμΌ λΉ¨λ¦¬ λμ°©ν μ μμμ§ μκ³ μΆλ€. μλλ μλμ°¨μ λν μ 보μ΄λ€.
| νλͺ© | μλμ°¨A | μλμ°¨B |
|---|---|---|
| μλ κ±°λλ° κ±Έλ¦¬λ μκ° | 3λΆ | 5μ΄ |
| λ¬Έ μ΄μλ€ λ«λ λ° κ±Έλ¦¬λ μκ° | 1λΆ | 0μ΄ |
| μ΄μ μ λ±λ°μ΄ μ‘°μ μ 걸리λ μκ° | 5λΆ | 0μ΄ |
| μ μ 리 λ¦λλ° κ±Έλ¦¬λ μκ° | 4λΆ | 0μ΄ |
| μ΅λ μμ | 200km/h | 40km/h |
μ¬μ€ μλμ°¨ Bλ μμ κ±°μ΄λ€. μλ κ±°λλ° κ±Έλ¦¬λ μκ°μ μ μΈνκ³ λ λ€λ₯Έ λΆκ°μ μΈ μκ°λ€μ΄ νμμμ§λ§, κ·Έλ λ€κ³ ν΄μ μμ κ±°λ₯Ό νκ³ μμΈμμ λΆμ°κΉμ§ κ°λ €λ μ¬λμ λ³λ‘ μμ κ²μ΄λ€.
- μ€λ 걸리λ νλͺ©λ€μ μ¬μ€ μΆλ°ν λ ν λ²λ§ μ μ©λλ λ°λ©΄, μ΅λ μμμ λ¬λ¦¬λ λ΄λ΄ μ μ©λκΈ° λλ¬Έμ΄λ€.
μ΄λ κ² ν κ°μ§ νλͺ©μ΄ μ 체μ λμλ₯Ό μ’μ§μ°μ§νλ κ²μ "μ§λ°°νλ€(dominate)"λΌκ³ νννλ€.
κ·ΈλΌ μκ³ λ¦¬μ¦μμ μν μκ°μ μ§λ°°νλ κ²μ 무μμΌκΉ? λ°λ‘ λ°λ³΅λ¬Έμ΄λ€.
-
μ λ ₯μ μκ΄μμ΄ νμ κ°μ μν μκ°μ κ°λ μκ³ λ¦¬μ¦λ μμ§λ§, λκ° μ λ ₯ ν¬κΈ°μ λ°λΌ μν νμκ° μ ν΄μ§λ λ°λ³΅λ¬Έμ΄ μκΈ° λ§λ ¨μ΄λ€.
- μ λ ₯μ΄ μμ μλ‘ λ°λ³΅ μΈμ λ€λ₯Έ μμλ€μ λΉμ€μ΄ ν΄ μ μμ§λ§, μ λ ₯μ΄ μ»€μ§ μλ‘ λ°λ³΅λ¬Έμ΄ μκ³ λ¦¬μ¦μ μν μκ°μ μ§λ°°νκ² λλ€.
λ°λΌμ, λκ° μκ³ λ¦¬μ¦μ μν μκ°μ λ°λ³΅λ¬Έμ΄ μνλλ νμλ‘ μΈ‘μ νλ€. (μ λ ₯μ ν¬κΈ°μ λν ν¨μλ‘ νν)
μλλ μ£Όμ΄μ§ λ°°μ΄μμ κ°μ₯ λ§μ΄ λ±μ₯νλ μλ₯Ό μ°Ύλ μ½λμ΄λ€. μν μκ°μ λ°°μ΄μ ν¬κΈ° N μ λ°λΌμ λ³νλ€. N λ² μνλλ λ°λ³΅λ¬Έμ΄ λ κ° κ²Ήμ³μμ΄ λ°λ³΅λ¬Έμ κ°μ₯ μμͺ½μ νμ N^2 λ² μ€νλκ³ , λ°λΌμ μ΄ μκ³ λ¦¬μ¦μ μν μκ°μ N^2 μ΄λ€.
private static int majority(int[] array) {
int N = array.length;
int majority = -1, majorityCnt = 0;
for (int i = 0; i < N; i++) {
// arrayμ λ±μ₯νλ μμμ μλ₯Ό μΌλ€.
int V = array[i], cnt = 0;
for (int j = 0; j < N; j++) {
if (V == array[j])
cnt++;
}
// μ§κΈκΉμ§μ μ΅λ λΉλμ λΉκ΅ ν μ΅μ ν
if (cnt > majorityCnt) {
majorityCnt = cnt;
majority = V;
}
}
return majority;
}
λ§μ½ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ μ«μλ€μ λ²μκ° μλ€λ©΄, λ°°μ΄μ μ΄μ©ν΄ κ° μ«μκ° λ±μ₯νλ νμλ₯Ό μ½κ² μ μ μκ³ , λ§μ§λ§μ λΉλμ λ°°μ΄μ μννλ©΄μ μ΅λμΉμ μμΉλ₯Ό μ°ΎμΌλ©΄ λλ€. μλ μ½λκ° μ΄λ₯Ό ꡬννλ€.
private static int majority2(int[] array) {
int N = array.length;
int[] frequency = new int[101];
for (int j : array) {
frequency[j]++;
}
int majority = 0;
for (int i = 1; i <= 100; i++) {
if (frequency[i] > frequency[majority])
majority = i;
}
return majority;
}
- λ°λ³΅λ¬Έμ΄ 2κ°κ° μλ€. νλλ
Nλ² μνλκ³ , νλλ 100λ² μνλλ€. κ³ λ‘ μ 체 μν νμλN + 100μ΄ λλ€. - κ·Έλ°λ°
Nμ΄ μ»€μ§λ©΄ μ»€μ§ μλ‘ μ¬μ€ 100λ² μννλ λ°λ³΅λ¬Έμ μν μκ°μμ μ°¨μ§νλ λΉμ€μ΄ μ€μ΄λ€κ² λλ€. λ°λΌμ κΆκ·Ήμ μΌλ‘λ μ΄ μκ³ λ¦¬μ¦μ μν μκ°μNμ΄λΌκ³ μ΄λ€.
π μ ν μκ° μκ³ λ¦¬μ¦
λ€μ΄μ΄νΈ νν© νμ
: μ΄λ νκ· κ³μ°νκΈ°
μ΄λ νκ· (moving average)μ μκ°μ λ°λΌ λ³ννλ κ°λ€μ κ΄μ°°ν λ μ μ©νκ² μ¬μ©ν μ μλ ν΅κ³μ κΈ°μ€μ΄λ€. Nκ°μ μΈ‘μ μΉκ° μ£Όμ΄μ§ λ λ§€λ¬ Mλ¬ κ°μ μ΄λ νκ· μ κ³μ°νλ νλ‘κ·Έλ¨μ μ΄λ»κ² μ§μΌ ν κΉ?
- κ° μμΉμμ μ§λ Mκ° μΈ‘μ μΉμ ν©μ ꡬνκ³ , μ΄λ₯Ό MμΌλ‘ λλλ€.
private static double[] movingAverage(double[] A, int M) {
int N = A.length;
double[] ret = new double[N];
int retIdx = 0;
for (int i = M-1; i < N; i++) {
double partialSum = 0;
for (int j = 0; j < M; j++)
partialSum += A[i-j];
ret[retIdx++] = partialSum/M;
}
return ret;
}
-
μ΄λ κ°λ¨νκ² λ κ°μ forλ¬Έμ μ¬μ©νλ μ½λλ‘ κ΅¬νν μ μλ€.
- μ¦ λ κ°μ forλ¬Έμ μν΄ μ§λ°°λλ€.
- μ΄ μ½λμ μν μκ°μ μ’ λ μ€μ΄λ λ°©λ²μ μμκΉ?
μ€μν μμ΄λμ΄λ μ€λ³΅λ κ³μ°μ μμ λ κ²μ΄λ€.
μΈ‘μ μΉκ° Mκ°λ λμ΄μΌ μ΄λ νκ· μ κ³μ°ν μ μμΌλ, νμ΄λ μ΄ν M-1μΌλΆν° μ΄λ νκ· μ κ³μ°ν μ μλ€.
- μλ νμμ M-1μΌμ μ΄λ νκ· κ³Ό MμΌμ μ΄λ νκ· μ ν¬ν¨λλ μ«μλ€μ μ°Ύμλ³Έλ€.
| λ μ§ | 0 | 1 | 2 | 3 | 4 | ... | M-1 | M | M+1 |
|---|---|---|---|---|---|---|---|---|---|
| λͺΈλ¬΄κ² | 3.5 | 3.5 | 3.5 | 3.6 | 3.5 | ... | 80.2 | 80.1 | 80.3 |
- 0μΌκ³Ό MμΌμ λͺΈλ¬΄κ²λ₯Ό μ μΈνλ©΄ μ λΆ κ²ΉμΉλ€λ κ²μ νμΈν μ μλ€.
- κ·Έλ λ€λ©΄ μΈ‘μ ν λͺΈλ¬΄κ²μ ν©μ μΌμΌμ΄ ꡬν νμ μμ΄ M-1μΌμ ꡬνλ λͺΈλ¬΄κ²μ ν©μμ 0μΌμ§Έμ μΈ‘μ ν λͺΈλ¬΄κ²λ₯Ό λΉΌκ³ MμΌμ§Έμ μΈ‘μ ν λͺΈλ¬΄κ²λ₯Ό λνλ©΄ λμ§ μμκΉ?
private static double[] movingAverage2(double[] A, int M) {
int N = A.length;
double[] ret = new double[N];
int retIdx = 0;
double partialSum = 0;
for (int i = 0; i < M-1; i++) partialSum += A[i];
for (int i = M-1; i < N; i++) {
partialSum += A[i];
ret[retIdx++] = partialSum/M;
partialSum -= A[i-M+1];
}
return ret;
}
- νλλ‘ λ¬Άμ¬μλ μ΄μ€ forλ¬Έμ λΆλ¦¬ν΄ λ°λ³΅λ¬Έμ μν νμλ₯Ό ν μ€μλ€.
-
μν μκ°μ Nμ μ λΉλ‘νκ² λκ³ , κ·Έλνλ‘ κ·Έλ €λ³΄λ©΄ μ νν μ§μ μ΄ λλ€.
- μ΄λ¬ν μκ³ λ¦¬μ¦μ μ ν μκ°(linear time) μκ³ λ¦¬μ¦μ΄λΌκ³ νλ€.
- μ΄λ° μκ³ λ¦¬μ¦μ΄ λκ° κ°μ₯ μ’μ μκ³ λ¦¬μ¦μΈ κ²½μ°κ° λ§λ€. μ£Όμ΄μ§ μ λ ₯μ μ΅μν ν λ²μ© μ³λ€λ³΄κΈ°λΌλ νλ €λ©΄ μ ν μκ°μ΄ 걸릴 μλ°μ μκΈ° λλ¬Έμ΄λ€!
π μ ν μ΄ν μκ³ λ¦¬μ¦
μ±ν μ μ¬μ§ μ°ΎκΈ°
μ΄λ€ λ¬Έμ 건 μ
λ ₯λ μλ£λ₯Ό λͺ¨λ ν λ² νλλ°λ μ
λ ₯μ ν¬κΈ°μ λΉλ‘νλ μκ°, μ¦ μ ν μκ°μ΄ κ±Έλ¦°λ€. κ·Έλ°λ° μ ν μ΄ν μκ³ λ¦¬μ¦μ κ·Έλ§νΌμ μκ°λ κ±Έλ¦¬μ§ μλλ€λ μλ―ΈμΈλ°, μ΄λ»κ² κ°λ₯ν κΉ? μ
λ ₯μΌλ‘ μ£Όμ΄μ§ μλ£μ λν΄ μ°λ¦¬κ° 미리 μκ³ μλ μ§μμ νμ©ν μ μλ€λ©΄ κ°λ₯ν΄μ§λ€.
μλ₯Ό λ€μ΄, μ΄λ€ μ°μμΈ Aκ΅°μ μ½ μ±ν μ κ³ λ±νκ΅ μ¬μ§μ΄ 곡κ°λμλ€. λ¨λ€ λͺ°λ Aκ΅°μ ν¬μΈ μ λ Aκ΅°μ΄ λ체 μΈμ μ±νμ νλμ§ μκ³ μΆμ΄ κ²μμμ§μΌλ‘ Aκ΅°μ μ¬μ§ 10λ§ μ₯μ μ°Ύμ μ΄λ€μ 촬μ λ μ§ μμΌλ‘ μ λ ¬νλ€. κ·ΈλΌ Aκ΅°μ΄ μΈμ μ±ννλμ§λ₯Ό κ°λ₯ν ν μ ννκ² μλ €λ©΄ λ체 λͺ μ₯μ μ¬μ§μ νμΈν΄μΌ ν κΉ?
-
10λ§μ₯μ μ¬μ§μ λͺ¨λ 보λ κ²μ μκ° λλΉμ΄λ―λ‘, λ¨μ μ¬μ§λ€μ νμ μ λ°μΌλ‘ λλ κ°μ΄λ° μλ μ¬μ§μ 보λ κ²μ΄λ€.
- λ¨Όμ κ°μ΄λ° μλ 5λ§ λ²μ§Έ μ¬μ§μ νμΈνμλ, μ½λ₯Ό μ±ννμ§ μμ μνλΌλ©΄ μ΄ μ μ μ¬μ§μ λ³Ό νμκ° μλ€. λΉμ°ν μ±νμ νμ§ μμ μνμ μ¬μ§λ€μΌ κ²μ΄λκΉ!
- μ΄λ‘μ νμΈν΄μΌ ν μ¬μ§μ΄ 5λ§μ₯μΌλ‘ μ€μκ³ , λ€μ κ·Έ μ€ κ°μ΄λ° μ¬μ§μ νμΈν΄ μμ κ³Όμ μ λμΌνκ² κ±°μΉλ€.
- νμΈν λλ§λ€ λ¨μ μ₯μκ° λλ΅ μ λ°μΌλ‘ μ€λ€λ©΄, μ΄ λͺ μ₯μ μ¬μ§μ νμΈν΄μΌ ν κΉ?
| νμΈν μ¬μ§μ μ | 0 | 1 | 2 | ... | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|
| λ¨μ μ¬μ§ | 100,000 | 50,000 | 25,000 | ... | 195 | 97 | 48 | 24 | 12 |
μ νλ νμΈνλ μ¬μ§μ μκ° μ¦κ°ν¨μ λ°λΌ λ¨μ μ¬μ§μ μκ° μ΄λ»κ² μ€μ΄λλμ§λ₯Ό 보μ¬μ€λ€. λλ΅ 17μ₯μ μ¬μ§λ§ νμΈνλ©΄ μ±νν μμ μ μ°ΎμλΌ μ μλ€.
- μ΄λ₯Ό λ΄μΌ νλ μ¬μ§μ μ₯μ Nμ λν΄ νννκ² λλ©΄, λ§€λ² μ λ°μ© λλλ λ°μ΄ 2μΈ λ‘κ·Έ λ₯Ό μ¬μ©νλ©΄ λκ³ , λ°λΌμ λλ΅ μ΄ λλ€.
- λ κ΅μ₯ν λλ¦¬κ² μ¦κ°νλ ν¨μμ΄λ€. μ΄μ κ°μ΄ μ λ ₯μ ν¬κΈ°κ° 컀μ§λ κ²λ³΄λ€ μν μκ°μ΄ λλ¦¬κ² μ¦κ°νλ μκ³ λ¦¬μ¦λ€μ μ ν μ΄ν μκ°(sublinear time) μκ³ λ¦¬μ¦μ΄λΌκ³ νλ€.
μ΄μ§ νμ
λ°©κΈ μ μμ μμ μ¬μ©ν μκ³ λ¦¬μ¦μ μ΄μ§ νμ(binary search)λΌκ³ νλ€.
binsearch(A[],x)= μ€λ¦μ°¨μμΌλ‘ μ λ ¬λ λ°°μ΄A[]μ μ°Ύκ³ μΆμ κ°xκ° μ£Όμ΄μ§ λA[i-1] < x <= A[i]μΈiλ₯Ό λ°ννλ€. μ΄λA[-1] = -β,A[N] = βλ‘ κ°μ νλ€.
-
μ½κ² μκ°ν΄μ, λ°°μ΄
A[]μμxλ₯Ό μ½μ ν μ μλ μμΉ μ€ κ°μ₯ μμ μλ κ²μ λ°ννλ ν¨μλΌκ³ μκ°νλ©΄ λλ€. λκ°μ λ°°μ΄μ΄λ 리μ€νΈ ꡬνμμiλ²μ§Έ μμΉμ μ μμλ₯Ό μ½μ νλ€ =iλ²μ§Έμ κ·Έ μ΄νμ μμλ€μ λ€λ‘ ν μΉΈμ© λ°μ΄λ΄κ³ λ€μ΄κ°λ€μ λμΌν μλ―Έμ΄λ€.- λ°λΌμ
A[]μxκ° μ‘΄μ¬νλ κ²½μ° μ΄ ν¨μλ 첫 λ²μ§Έxμ μμΉλ₯Ό λ°ννκ³ , μλ κ²½μ°xλ³΄λ€ ν° μ²« λ²μ§Έ μμλ₯Ό λ°ννλ€.
- λ°λΌμ
κ·Έλλ μ ν μκ° μλκ°μ?
κ·Έλ°λ° binsearch() μ μ
λ ₯λλ λ°°μ΄μ λ§λ€κΈ° μν΄μλ κ²°κ΅ λͺ¨λ μ¬μ§μ 보면μ μ±ν μ΄μ μΈμ§ μ¬λΆλ₯Ό νλ¨ν΄μΌ νλ€. κ²λ€κ° κ·Έ μ μ λͺ¨λ μ¬μ§μ λ°μ μκ° μμΌλ‘ μ λ ¬κΉμ§ ν΄μΌ νλ€. λ°λΌμ μ 체λ μ ν μκ°μ΄ 걸리λ κ² μλκ° νλ μλ¬Έμ΄ λ λ€. νμ§λ§ μ΄λ κ² λΆμνμ§ μλ μ΄μ λ λ€μκ³Ό κ°λ€.
-
A[]λ₯Ό μ€μ λ‘ κ³μ°ν΄μ κ°μ§κ³ μμ νμκ° μλ€. μ¬μ€μ μ λ ₯ λ°°μ΄μ λ겨μ€λ€ν΄λ, μ΄μ§ νμ μκ³ λ¦¬μ¦ λ΄λΆμμλ κ·Έ μ€ λͺ κ° λ³΄μ§λ μμ κ²μ΄λ€. λ°λΌμ μ΄λ€μ 미리 κ³μ°ν κ²μ΄ μλλΌ, κ°μ΄λ° μλ κ²λ€μ λν΄μλ§ νμν λ κ³μ°(μ±ν μ¬λΆλ₯Ό νλ¨)νλ©΄ λλ€.binsearch()μA[]λ₯Ό μΈμλ‘ λκΈ°λ κ²μ΄ μλiκ° μ£Όμ΄μ§ λA[i]μ κ°μ μ§μ κ³μ°νλ μ½λ°± ν¨μλ₯Ό μ 곡νλ€κ±°λ νλ λ°©λ²μΌλ‘ ν΄κ²° κ°λ₯νλ€.
- μ¬μ§μ λ€μ΄λ°κ³ μ λ ¬νλ κ³Όμ μ μ€μ λ‘ μ±ν μ μ¬μ§μ μ°Ύλ μμ κ³Όλ λ³κ°μ΄λ€. λ§μ½ Aκ΅°μ΄ μ½λΏλ§ μλλΌ ν±κΉμ§λ μ±νμ νλ€κ³ νλ©΄, μ΄λ―Έ ν λ² λ°μμ μ λ ¬ν΄λ μ¬μ§μ΄ μμΌλ©΄ λ€μ 17μ₯μ μ¬μ§λ§ νμΈν΄μ μΈμ ν± μ±νμ νλμ§ μ μ μμ κ²μ΄λ€.
ꡬν
μ΄μ§ νμμ μ ννκ² κ΅¬ννλ κ²μ λ§€μ° κΉλ€λ‘λ€. μ΄λ μκ³ λ¦¬μ¦μ μ λΉμ±μ μ¦λͺ
νλ λ°©λ²μ λ€λ£° λ λ€μ μΈκΈνλ€.
π μ§μ μκ° μκ³ λ¦¬μ¦
λ€ν μκ° μκ³ λ¦¬μ¦
"λ°λ³΅λ¬Έμ μν νμλ₯Ό μ
λ ₯ ν¬κΈ°μ λ€νμμΌλ‘ ννν μ μλ μκ³ λ¦¬μ¦"λ€μ λ€ν μκ° μκ³ λ¦¬μ¦μ΄λΌκ³ νλ€.
- λ€ν μκ°μ΄λΌλ νλμ λΆλ₯μ ν¬ν¨λλ μκ³ λ¦¬μ¦ κ°μλ μμ²λκ² ν° μκ° μ°¨μ΄κ° λ μ μλ€. (λ€νμμ ν¬ν¨ λ²μ£Όκ° λ§€μ° ν¬κΈ° λλ¬Έ)
- λ€ν μκ°λ³΄λ€ λλμ± μ€λ μκ°μ΄ 걸리λ μκ³ λ¦¬μ¦λ€μ΄ μμ΄ λ€ν μκ° μκ³ λ¦¬μ¦μ λ¬Άμλ€.
μλ¬μ§κ° μ¬ν μΉκ΅¬λ€
μ§λ€μ΄μ Nλͺ
μ μΉκ΅¬λ₯Ό μ΄λνλ €κ³ νλ€. ν μ€ μλ Mκ°μ§ μμ μ€ λ¬΄μμ λμ ν΄μΌ ν κΉλ₯Ό κ³ λ―Όνλλ°, μΉκ΅¬λ€μ κ°κ° μλ¬μ§ λλ¬Έμ λͺ» λ¨Ήλ μμλ€μ΄ μλ€. λ§λ€ μ€ μλ μμμ λͺ©λ‘κ³Ό, ν΄λΉ μμμ λͺ» λ¨Ήλ μΉκ΅¬λ€μ λͺ©λ‘μ΄ μ£Όμ΄μ§ λ, κ° μΉκ΅¬κ° λ¨Ήμ μ μλ μμμ΄ μ΅μ νλμ© μμΌλ €λ©΄ μ΅μ λͺ κ°μ§μ μμμ ν΄μΌ ν κΉ?
λͺ¨λ λ΅ ν보λ₯Ό νκ°νκΈ°
μ¬λ¬ κ°μ λ΅μ΄ μ‘΄μ¬ν μ μλ€. νμ§λ§ μ΅μ κ°μμ λ΅μ ꡬνλ €κ³ ν λ, κ°μ₯ κ°λ¨ν λ°©λ²μ λͺ¨λ λ΅μ μΌμΌμ΄ κ³ λ €ν΄ λ³΄λ κ²μ΄λ€.
- λ§λ€ μ μλ μμμ λͺ¨λ λͺ©λ‘μ λ§λλ κ³Όμ μ μ¬λ¬ κ°μ κ²°μ μΌλ‘ λλλ©΄ μμ°μ€λ½λ€.
-
첫 λ²μ§Έ μ리λ₯Ό λ§λ€μ§ λ§μ§ κ²°μ νκ³ , λ λ²μ§Έ μ리λ₯Ό λ§λ€μ§ λ§μ§λ₯Ό κ²°μ νλ λ°©μμ΄λ€. μ΄λ κ² μ μ§μ μΌλ‘ κ²°μ νλ€λ³΄λ©΄, λ§μ§λ§μλ μ‘΄μ¬ κ°λ₯ν λͺ¨λ λͺ©λ‘μ λ§λ μ μλ€.
- μ΄μ κ°μ₯ μ μ μμ λͺ©λ‘μ μ°Ύλλ€.
μ΄λ° μκ³ λ¦¬μ¦μ ꡬννλ κ°μ₯ μ¬μ΄ λ°©λ²μ μ¬κ· νΈμΆμ μ΄μ©νλ κ²μ΄λ€.
- μ΄λ μ¬κ· ν¨μλ ν μνλ₯Ό μ λ ₯λ°μ μ΄ μν λ°μ λ¬λ¦° λͺ¨λ ν보λ€μ κ²μ¬νκ³ μ΄ μ€ κ°μ₯ μ’μ λ΅μ λ°ννλ μν μ νλ€.
int INF = 987654321;
int M;
private static boolean canEverybodyEat(Stack<Integer> menu) { ... }
private static int selectMenu(Stack<Integer> menu, int food) {
if (food == M) {
if (canEverybodyEat(menu)) return menu.length;
return INF;
}
int ret = selectMenu(menu, food + 1);
menu.push(food);
ret = Math.min(ret, selectMenu(menu, food + 1));
menu.pop();
return ret;
}
μ§μ μκ° μκ³ λ¦¬μ¦
μ νλ‘κ·Έλ¨μ λͺ¨λ λ΅μ ν λ²μ© λ€ νμΈνκΈ°μ, μ 체 걸리λ μκ°μ λ§λ€ μ μλ λ΅μ μμ λΉλ‘νκ² λλ€.
- Mκ°μ§μ μμλ§λ€ λ μ νμ§κ° μμ΄ λ§λ€ μ μλ λ΅μ λͺ¨λ κ°μ§μ΄λ€.
- κ·Έλ¦¬κ³ λ΅μ νλ λ§λ€ λλ§λ€
canEverybodyEat()λ₯Ό μνν΄ μ΄ μκ³ λ¦¬μ¦μ μν μκ°μ μcanEverybodyEat()μ μν μκ°μ κ³±ν κ²μ΄ λλ€. -
κ³Ό κ°μ μ§μ ν¨μλ μκ³ λ¦¬μ¦μ μ 체 μν μκ°μ μμ²λ μν₯μ λ―ΈμΉλ€. μ΄μ κ°μ΄ Nμ΄ νλ μ¦κ°ν λλ§λ€ 걸리λ μκ°μ΄ λ°°λ‘ μ¦κ°νλ μκ³ λ¦¬μ¦λ€μ μ§μ μκ°(exponential time)μ λμνλ€κ³ νλ€.
- κ°μ₯ ν° μν μκ° μ€ νλμ΄λ€.
μμΈμ λΆν΄μ μν μκ°
μ
λ ₯μΌλ‘ μ£Όμ΄μ§λ μ«μμ κ°μκ° μλλΌ κ·Έ ν¬κΈ°μ λ°λΌ μν μκ°μ΄ λ¬λΌμ§λ μκ³ λ¦¬μ¦λ€ λν μ§μ μν μκ°μ κ°μ§ μ μλ€.
- μμ°μ Nμ΄ μ£Όμ΄μ§ λ Nμ μμΈμ λΆν΄ κ²°κ³Όλ₯Ό λ°ννλ κ°λ¨ν μκ³ λ¦¬μ¦μ΄ μλ€.
- μ΄ μκ³ λ¦¬μ¦μ Nμ΄ 1μ΄ λ λκΉμ§ κ°λ₯ν λͺ¨λ μ«μλ‘ Nμ λλ 보λλ°, μ£Όμ΄μ§ μ Nμ΄ μμμΈ κ²½μ° λ°λ³΅λ¬Έμ΄ κ°μ₯ λ§μ΄ μ€νλλ€.
κ²°κ³Όμ μΌλ‘ λ°λ³΅λ¬Έμ μ€ν νμλ N - 1μ΄ λμ΄, μ€ν νμκ° λλ΅ Nμ λΉλ‘ν΄ μ΅μ μ κ²½μ° μ ν μκ°μ΄ κ±Έλ¦°λ€κ³ μκ°ν μλ μλ€.
μ΄λ° λΆμΌμΉλ₯Ό μ§κ΄μ μΌλ‘ μ΄ν΄νκΈ° μν΄ μκ³ λ¦¬μ¦μ μν μκ°κ³Ό μ λ ₯μ΄ λ©λͺ¨λ¦¬μμ μ°¨μ§νλ 곡κ°μ κ΄κ³λ₯Ό μκ°ν΄λ³΄μ.
-
μ΄μ§ νμ, μ΄λ νκ· κ³μ° λ± μ§κΈκΉμ§ λ€λ£¬ μκ³ λ¦¬μ¦μμλ μ λ ₯μ κ°λ€μ΄ μΌμ λ²μ λ΄μ μλ€κ³ μ΄λ ΅μ§ μκ² κ°μ ν μ μλ€.
- μ΄ κ²½μ° μ λ ₯μ κ°μμ λ©λͺ¨λ¦¬μμ μ°¨μ§νλ 곡κ°μ΄ μ§μ μ μΌλ‘ λΉλ‘νλ€.
-
λ°λ©΄, μμΈμ λΆν΄ λ¬Έμ μμλ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ μ«μκ° μκ³ λ¦¬μ¦μ λμμ μ§μ μ μΈ μν₯μ λ―Έμ³, μ«μκ° νΉμ λ²μ μμ μλ€κ³ κ°μ ν μ μλ€.
- μ λ ₯μ κ°μ΄ 컀μ§μλ‘ μ«μλ₯Ό μ μ₯νλλ° νμν λ©λͺ¨λ¦¬μ 곡κ°λ μ¦κ°ν κ²μ΄λ€.
- μ΄λ μ λ ₯μ΄ μ°¨μ§νλ λΉνΈμ μμ λ°λΌ μν μκ°μ΄ μ¦κ°νλ€κ³ μκ°νλ©΄ μκΉμ λΆμΌμΉλ₯Ό μ§κ΄μ μΌλ‘ μ€λͺ ν μ μλ€.
π μκ° λ³΅μ‘λ
π μν μκ° μ΄λ¦Όμ§μνκΈ°
π κ³μ° 볡μ‘λ ν΄λμ€: P, NP, NP-μλΉ
π μ°Έκ³
νλ‘κ·Έλλ° λνμμ λ°°μ°λ μκ³ λ¦¬μ¦ λ¬Έμ ν΄κ²° μ λ΅ - κ΅¬μ’ λ§